package com.sheng.leetcode.year2023.month02.day07;

import org.junit.Test;

import java.util.*;

/**
 * @author liusheng
 * @date 2023/02/07
 * <p>
 * 1604. 警告一小时内使用相同员工卡大于等于三次的人<p>
 * <p>
 * 力扣公司的员工都使用员工卡来开办公室的门。每当一个员工使用一次他的员工卡，安保系统会记录下员工的名字和使用时间。<p>
 * 如果一个员工在一小时时间内使用员工卡的次数大于等于三次，这个系统会自动发布一个 警告 。<p>
 * 给你字符串数组 keyName 和 keyTime ，其中 [keyName[i], keyTime[i]] 对应一个人的名字和他在 某一天 内使用员工卡的时间。<p>
 * 使用时间的格式是 24小时制 ，形如 "HH:MM" ，比方说 "23:51" 和 "09:49" 。<p>
 * 请你返回去重后的收到系统警告的员工名字，将它们按 字典序升序 排序后返回。<p>
 * 请注意 "10:00" - "11:00" 视为一个小时时间范围内，而 "23:51" - "00:10" 不被视为一小时内，因为系统记录的是某一天内的使用情况。<p>
 * <p>
 * 示例 1：<p>
 * 输入：keyName = ["daniel","daniel","daniel","luis","luis","luis","luis"], keyTime = ["10:00","10:40","11:00","09:00","11:00","13:00","15:00"]<p>
 * 输出：["daniel"]<p>
 * 解释："daniel" 在一小时内使用了 3 次员工卡（"10:00"，"10:40"，"11:00"）。<p>
 * <p>
 * 示例 2：<p>
 * 输入：keyName = ["alice","alice","alice","bob","bob","bob","bob"], keyTime = ["12:01","12:00","18:00","21:00","21:20","21:30","23:00"]<p>
 * 输出：["bob"]<p>
 * 解释："bob" 在一小时内使用了 3 次员工卡（"21:00"，"21:20"，"21:30"）。<p>
 * <p>
 * 示例 3：<p>
 * 输入：keyName = ["john","john","john"], keyTime = ["23:58","23:59","00:01"]<p>
 * 输出：[]<p>
 * <p>
 * 示例 4：<p>
 * 输入：keyName = ["leslie","leslie","leslie","clare","clare","clare","clare"], keyTime = ["13:00","13:20","14:00","18:00","18:51","19:30","19:49"]<p>
 * 输出：["clare","leslie"]<p>
 * <p>
 * 提示：<p>
 * 1 <= keyName.length, keyTime.length <= 10^5<p>
 * keyName.length == keyTime.length<p>
 * keyTime 格式为 "HH:MM" 。<p>
 * 保证 [keyName[i], keyTime[i]] 形成的二元对 互不相同 。<p>
 * 1 <= keyName[i].length <= 10<p>
 * keyName[i] 只包含小写英文字母。<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/alert-using-same-key-card-three-or-more-times-in-a-one-hour-period">1604. 警告一小时内使用相同员工卡大于等于三次的人</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1604 {

    @Test
    public void test01() {
//        String[] keyName = {"daniel", "daniel", "daniel", "luis", "luis", "luis", "luis"}, keyTime = {"10:00", "10:40", "11:00", "09:00", "11:00", "13:00", "15:00"};
//        String[] keyName = {"alice", "alice", "alice", "bob", "bob", "bob", "bob"}, keyTime = {"12:01", "12:00", "18:00", "21:00", "21:20", "21:30", "23:00"};
//        String[] keyName = {"john", "john", "john"}, keyTime = {"23:58", "23:59", "00:01"};
//        String[] keyName = {"leslie", "leslie", "leslie", "clare", "clare", "clare", "clare"}, keyTime = {"13:00", "13:20", "14:00", "18:00", "18:51", "19:30", "19:49"};
        String[] keyName = {"a", "a", "a", "a", "a", "b", "b", "b", "b", "b", "b"}, keyTime = {"04:48", "23:53", "06:36", "07:45", "12:16", "00:52", "10:59", "17:16", "00:36", "01:26", "22:42"};
        System.out.println(new Solution().alertNames(keyName, keyTime));
    }
}

class Solution {
    public List<String> alertNames(String[] keyName, String[] keyTime) {
        List<String> list = new ArrayList<>();
        Map<String, List<String>> map = new HashMap<>(16);
        for (int i = 0; i < keyName.length; i++) {
            List<String> orDefault = map.getOrDefault(keyName[i], new ArrayList<>());
            orDefault.add(keyTime[i]);
            map.put(keyName[i], orDefault);
        }
        for (Map.Entry<String, List<String>> entry : map.entrySet()) {
            if (entry.getValue().size() < 3) {
                continue;
            }
            LinkedList<String> strings = new LinkedList<>();
            entry.getValue().sort(String::compareTo);
            for (String string : entry.getValue()) {
                strings.addLast(string);
                if (strings.size() == 3) {
                    // 验证这三个时间段在一个小时内，则将名字添加到返回集合中并结束本次循环，否则，删除掉第一个元素
                    String[] s1 = strings.get(0).split(":");
                    String[] s3 = strings.get(2).split(":");
                    if (s1[0].equals(s3[0]) || (Integer.parseInt(s1[0]) + 1 == Integer.parseInt(s3[0]) && Integer.parseInt(s1[1]) >= Integer.parseInt(s3[1]))) {
                        list.add(entry.getKey());
                    } else {
                        strings.pollFirst();
                    }
                }
            }
        }
        list.sort(String::compareTo);
        return list;
    }
}
